//统计公司员工最爱的前k种水果

#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <queue>
using namespace std;

struct compair
{
    bool operator()(const pair<string, int>& l,const pair<string, int>& r)
    {
        return l.second < r.second;
    }
};

struct compairiterator
{
    bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
    {
        return l->second > r->second;
    }
};

//void  Getkfruit(vector<string>& str, int k)
//{
//    map<string, int> countmap;
//    for (auto& fruit : str)
//    {
//        countmap[fruit]++;
//    }
//    vector<pair<string, int>> countv;
//    for (auto& pair : countmap)
//    {
//        countv.push_back(pair);
//    }
//    sort(countv.begin(), countv.end(), compair());
//    for (int i = 0; i < k; i++)
//    {
//        cout << countv[i].first << ": " << countv[i].second << endl;
//    }
//}

//void  Getkfruit(vector<string>& str, int k)
//{
//    map<string, int> countmap;
//    for (auto& fruit : str)
//    {
//        countmap[fruit]++;
//    }
//    vector<map<string,int>::iterator> countv;
//    auto it = countmap.begin();
//    while(it!=countmap.end())
//    {
//        countv.push_back(it);
//        ++it;
//    }
//    sort(countv.begin(), countv.end(), compairiterator());
//    for (int i = 0; i < k; i++)
//   {
//     cout << countv[i]->first << ": " << countv[i]->second << endl;
//   }
//}

//void  Getkfruit(vector<string>& str, int k)
//{
//    map<string, int> countmap;
//    for (auto& fruit : str)
//    {
//        countmap[fruit]++;
//    }
//    multimap<int, string,greater<>> sortmap;
//    for (auto &pair : countmap)
//    {
//        sortmap.insert(make_pair(pair.second, pair.first));
//    }
//    auto it = sortmap.begin();
//    while (k--)
//    {
//        cout << it->second << ": " << it->first << endl;
//        ++it;
//    }
//}

void  Getkfruit(vector<string>& str, int k)
{
    map<string, int> countmap;
    for (auto& fruit : str)
    {
        countmap[fruit]++;
    }
    priority_queue<pair<string, int>, vector<pair<string, int>>, compair> pq;
    for (auto& pair : countmap)
    {
        pq.push(pair);
    }
    while (k--)
    {
        cout << pq.top().first << ": " << pq.top().second << endl;
        pq.pop();
    }

}


int main()
{
    vector<string> fruits = { "苹果","香蕉","梨","荔枝","苹果","榴莲","榴莲","榴莲","香蕉","苹果","苹果","榴莲","苹果" };
    Getkfruit(fruits, 3);
    return 0;
}
